Methods for coding vector or matrix quantities for speech, audio, image, video, and other signals are well known. One such method described in U.S. Pat. No. 6,236,960 by Peng, et. al, (which is incorporated by reference herein) is known as Factorial Pulse Coding (or FPC). FPC can code a vector xi using a total of M bits, given that:
                              m          =                                    ∑                              i                =                0                                            n                -                1                                      ⁢                                                        x                i                                                                  ,                            (        1        )            and all values of vector xi are integral valued such that −m≦xi≦m, where m is the total number of unit amplitude pulses, and n is the vector length. The total M bits are used to code N combinations in a maximally efficient manner, such that the following expression, which describes the theoretical minimum number of combinations, holds true:
                    N        =                                            ∑                              d                =                1                                            min                ⁡                                  (                                      m                    ,                    n                                    )                                                      ⁢                                          F                ⁡                                  (                                      n                    ,                    d                                    )                                            ⁢                              D                ⁡                                  (                                      m                    ,                    d                                    )                                            ⁢                              2                d                                              ≤                                    2              M                        .                                              (        2        )            For this equation, F(n,d) are the number of combinations of d non-zero vector elements over n positions given by:
                                          F            ⁡                          (                              n                ,                d                            )                                =                                    n              !                                                      d                !                            ⁢                                                (                                      n                    -                    d                                    )                                !                                                    ,                            (        3        )            D(m,d) are the number of combinations of d non-zero vector elements given m total unit pulses given by:D(m,d)=F(m−1,d−1),  (4)and 2d represents the combinations required to describe the polarity (sign) of the d non-zero vector elements. The term min(m, n) allows for the case where the number of unit magnitude pulses m exceeds the vector length n. A method and apparatus for coding and decoding vectors of this form have been fully described in the prior art. Furthermore, a practical implementation of this coding method has been described in 3GPP2 standard C.S0014-B, where the vector length n=54 and the number of unit magnitude pulses m=7 produce an M=35 bit codeword.
While these values of n and m do not cause any unreasonable complexity burden, larger values can quickly cause problems, especially in mobile handheld devices which need to keep memory and computational complexity as low as possible. For example, use of this coding method for some applications (such as audio coding) may require n=144 and m=28, or higher. Under these circumstances, the cost associated with producing the combinatorial expression F(n,d) using prior art methods may be too high for practical implementation.
In looking at this cost in greater detail, we can rewrite Eq. 3 as:
                              F          ⁡                      (                          n              ,              d                        )                          =                                                            ∏                                  i                  =                                      n                    -                    d                    +                    1                                                  n                            ⁢                              (                i                )                                                                    ∏                                  j                  =                  1                                d                            ⁢                              (                j                )                                              .                                    (        5        )            Direct implementation is problematic because F(144, 28) would require 197 bits of precision in the numerator and 98 bits of precision in the nominator to produce a 99 bit quotient. Since most digital signal processors (DSPs) used in today's handheld devices typically support only 16 bit×16 bit multiply operations, special multi-precision multiply/divide routines would need to be employed. Such routines require a series of nested multiply/accumulate operations that typically require on the order of k multiple/accumulate (MAC) operations, where k is the number of 16 bit segments in the operand. For a 197 bit operand, k=┌197/16┐=13. So, execution of a single 197×16 bit multiply would require a minimum of 13 MAC operations plus shifting and store operations. The denominator term is calculated in a similar manner to produce a 98 bit result. In addition, a 197/98 bit division is required, which is an extremely complex operation, thus computation of the entire factorial relation in Eq. 5 would require considerable resources.
In an effort to reduce complexity, Eq. 5 can be rewritten in to distribute the divide operations to produce the following:
                              F          ⁡                      (                          n              ,              d                        )                          =                  round          ⁡                      [                                                            (                                      n                    d                                    )                                ·                                  (                                                            n                      -                      1                                                              d                      -                      1                                                        )                                ·                                  (                                                            n                      -                      2                                                              d                      -                      2                                                        )                                            ⁢                                                          ⁢              …              ⁢                                                          ⁢                                                (                                                            n                      -                      d                      +                      2                                        2                                    )                                ·                                  (                                                            n                      -                      d                      +                      1                                        1                                    )                                                      ]                                              (        6        )            In this expression, the dynamic range of the divide operations is reduced, but unfortunately, increased resolution of the quotient is needed to accurately represent division by 3, 7, 9, etc. In order to accommodate this structure, a rounding operation is also needed to guarantee an integer result. Given the large number of high precision divide operations, this implementation does not adequately address the complexity problem for large m and n, and further has the potential to produce an incorrect result due to accumulated errors in precision.
In yet another implementation, Eq. 5 can be rearranged in the following manner:
                              F          ⁡                      (                          n              ,              d                        )                          =                              n            ·                          (                              n                -                1                            )                        ·                          (                              1                2                            )                        ·                          (                              n                -                2                            )                        ·                                                  ⁢                                                  ⁢                          (                              1                3                            )                                ⁢                                          ⁢          …          ⁢                                          ⁢                                    (                              n                -                d                +                2                            )                        ·                          (                              1                                  d                  -                  1                                            )                        ·                          (                              n                -                d                +                1                            )                        ·                                          (                                  1                  d                                )                            .                                                          (        7        )            If this expression is evaluated from left to right, the result will always produce an integer value. While this method controls the precision and dynamic range issue to some degree, large values of m and n still require extensive use of multi-precision multiply and divide operations.
Finally, in order to minimize computational complexity, it may be possible to pre-compute and store all factorial combinations in a lookup table. Thus, all values of F(n,m) may be simply stored in an n×m matrix and appropriately retrieved from memory using very few processor cycles. The problem with this approach, however, is that as n and m become large, so does the associated memory requirement. Citing the previous example, F(144, 28) would require 144×28×┌99 bits/8 bits/byte┐=52,416 bytes of storage, which is unreasonable for most mobile handheld devices. Therefore, a need exists for a method and apparatus for low-complexity combinational Factorial Pulse Coding of vectors.